home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / programm.ing / graphx11.zoo / demos / sort.c < prev   
Encoding:
C/C++ Source or Header  |  1992-08-06  |  10.8 KB  |  334 lines
  1. /*****************************************************************************/
  2. /*      File    : SORT.C                        Copyright (c) 1992           */
  3. /*                                                                           */
  4. /*      Author  : Kenneth W. Hartlen                                         */
  5. /*      Address : Box 37, Site 6, RR#3                                       */
  6. /*                Armdale, Nova Scotia                                       */
  7. /*                B3L 4J3 Canada                                             */
  8. /*                                                                           */
  9. /*      Purpose : Simple program that uses graphics commands and can be      */
  10. /*                be compiled in Lattice C, Sozobon C and Turbo C.         */
  11. /*                                                                           */
  12. /*                This programs show, graphically, how the bubble sort,      */
  13. /*                insertion sort, selection sort and quick sort work.        */
  14. /*                                                                           */
  15. /*                Insertion sort and selection sort algorithms from:         */
  16. /*                "Data Structures and Progam Design", Robert L. Kruse       */
  17. /*                                                                           */
  18. /*                Quick sort algorithm from:                                 */
  19. /*                "The C Programming Language", 2nd Ed., Kernighan & Ritchie */
  20. /*****************************************************************************/
  21. /*      Compiling with Lattice C:                                            */
  22. /*              lc.ttp -fm sort.c                                            */
  23. /*              clink.ttp c.o+sort.o                                         */
  24. /*                      LIB graphics.lib+lcm.lib+lcg.lib+lc.lib              */
  25. /*                      TO sort.prg                                          */
  26. /*                                                                           */
  27. /*      Compiling with Sozobon C:                                            */
  28. /*              cc -c sort.c                                                 */
  29. /*              cc -o sort.prg -r sort.o graphics.a aesfast.a vdifast.a      */
  30. /*                                                                           */
  31. /*    Compiling with Heat & Serve Sozobon C v1.33i:                 */
  32. /*        cc -c lines.c                             */
  33. /*        cc -o lines.prg lines.o graphics.a libm.a aesfast.a \         */
  34. /*                vdifast.a                     */
  35. /*                                                                           */
  36. /*      Compile with Turbo C:                                                */
  37. /*              Use Turbo C's IDE                                            */
  38. /*                                                                           */
  39. /*****************************************************************************/
  40.  
  41. #ifdef    SOZOBON
  42. #define __MAIN_SRC__                    /* to be included with user's source */
  43. #endif
  44.  
  45. #include <stdio.h>                      /* common header files */
  46. #include <graphics.h>
  47.  
  48. #ifndef    SOZOBON                /* includes for Lattice and Turbo */
  49. #include <stdlib.h>
  50. #include <dos.h>
  51. #endif
  52.  
  53. #ifndef    __TURBOC__            /* includes for Lattice and Sozobon */
  54. #include <osbind.h>
  55. #endif
  56.  
  57. /*****************************************************************************/
  58. /*  Main program loop                                                        */
  59. /*****************************************************************************/
  60.  
  61. #define NUMPOINTS       100             /* maximum # of lines to display */
  62.  
  63. int     maxX,                           /* save getmaxx() result */
  64.         maxY,                           /* save getmaxy() result */
  65.         numcolours,
  66.         width,
  67.         points[NUMPOINTS],              /* array holding values */
  68.         seed;                           /* random number seed */
  69.  
  70. #ifdef __TURBOC__
  71. struct time now;
  72. #endif
  73.  
  74. /*****************************************************************************/
  75. /*      Function prototypes                                                  */
  76. void build_list();
  77. void display_graph();
  78. void update_graph();
  79. void pause();
  80.  
  81. int maxkey();
  82. void swap();
  83.  
  84. void bubble_sort();
  85. void insertion_sort();
  86. void selection_sort();
  87.  
  88. void q_sort();
  89. void quick_sort();
  90.  
  91. /*****************************************************************************/
  92. void main()
  93. {
  94. int     graphdriver = DETECT, graphmode;
  95.  
  96.  
  97.     /* initialize graphics */
  98.     initgraph(&graphdriver,&graphmode,"");
  99.  
  100.     maxX = getmaxx();                   /* save values to eliminate     */
  101.     maxY = getmaxy() - textheight("H"); /* function call in the do loop */
  102.     numcolours = getmaxcolor();
  103.     width = maxX / NUMPOINTS;
  104.  
  105.     /* Display Title screen */
  106.     setcolor(WHITE);
  107.     settextjustify(CENTER_TEXT,TOP_TEXT);
  108.     outtextxy(maxX/2,maxY/3,"SORT DEMO");
  109.     outtextxy(maxX/2,maxY/3+textheight("H")*2,"by Kenneth W. Hartlen");
  110.     outtextxy(maxX/2,maxY/3+textheight("H")*4,"Copyright (c) 1992");
  111.     outtextxy(maxX/2,maxY/3+textheight("H")*7,"press a key to continue");
  112.     rectangle(0,0,maxX,maxY);
  113.     getch();
  114.  
  115.     /* initialize variables */
  116.     #ifdef __TURBOC__                   /* get system time for use as the */
  117.     gettime(&now);                      /* random number generator seed   */
  118.     seed = now.ti_sec;
  119.     #else
  120.     seed = Tgettime();
  121.     #endif
  122.  
  123.     build_list(seed,points,NUMPOINTS);
  124.     display_graph(points,NUMPOINTS,"Bubble Sort");
  125.     bubble_sort(points,NUMPOINTS);
  126.     pause("Press any key to continue...");
  127.  
  128.     build_list(seed,points,NUMPOINTS);
  129.     display_graph(points,NUMPOINTS,"Insertion Sort");
  130.     insertion_sort(points,NUMPOINTS);
  131.     pause("Press any key to continue...");
  132.  
  133.     build_list(seed,points,NUMPOINTS);
  134.     display_graph(points,NUMPOINTS,"Selection Sort");
  135.     selection_sort(points,NUMPOINTS);
  136.     pause("Press any key to continue...");
  137.  
  138.     build_list(seed,points,NUMPOINTS);
  139.     display_graph(points,NUMPOINTS,"Quick Sort");
  140.     quick_sort(points,NUMPOINTS);
  141.     pause("Demo finished. Press any key...");
  142.     
  143.     closegraph();                       /* close graphics */
  144.     return;
  145.         
  146. } /* main */
  147.  
  148. /*****************************************************************************/
  149. /*      Generate a list of random number to sort                             */
  150. void build_list(seed, points, num)
  151. int seed, points[], num;
  152. {
  153. int     i;
  154.  
  155.     srand(seed);    
  156.     for(i=0;i<num;i++)
  157.         points[i] = rand() % maxY;
  158.  
  159. }
  160.  
  161. /*****************************************************************************/
  162. /*      Display a graph of the list                                          */
  163. void display_graph(points, num, name)
  164. int points[], num;
  165. char *name;
  166. {
  167. int     i,pat,col;
  168.     
  169.     cleardevice();
  170.     rectangle(0,0,(width*num)+2,maxY);
  171.     settextjustify(LEFT_TEXT,TOP_TEXT);
  172.     outtextxy(0,maxY+1,"0");
  173.     outtextxy( (width*num)-textwidth("99"),maxY+1,"99");
  174.     settextjustify(CENTER_TEXT,TOP_TEXT);
  175.     outtextxy((width*num)/2,maxY+1,name);
  176.         
  177.     for(i=0;i<num;i++) {
  178.         if (numcolours == 1) {
  179.             pat=((points[i] * 12) / maxY ) + 1;
  180.             setfillstyle(pat,WHITE);
  181.         }
  182.         else {
  183.             col=((points[i] * numcolours) / maxY ) + 1;
  184.             setfillstyle(SOLID_FILL,col);
  185.         }
  186.         bar((i*width)+1,maxY-points[i],((i+1)*width)-1,maxY);
  187.     }
  188.     
  189. }
  190.  
  191. /*****************************************************************************/
  192. /*      Update the graph                                                     */
  193. void update_graph(points, i)
  194. int points[], i;
  195. {
  196. int     pat,col;
  197.     
  198.     if (numcolours == 1) {
  199.         pat=((points[i] * 12) / maxY ) + 1;
  200.         setfillstyle(pat,WHITE);
  201.     }
  202.     else {
  203.         col=((points[i] * numcolours) / maxY ) + 1;
  204.         setfillstyle(SOLID_FILL,col);
  205.     }
  206.     bar((i*width)+1,maxY-points[i],((i+1)*width)-1,maxY);
  207.  
  208.     setfillstyle(SOLID_FILL, BLACK);
  209.     bar((i*width)+1,1,((i+1)*width)-1,maxY-points[i]-1);
  210.     
  211. }
  212.  
  213. /*****************************************************************************/
  214. /*      Wait for user to press a key                                         */
  215.  
  216. void pause(msg)
  217. char *msg;
  218. {
  219.     settextjustify(CENTER_TEXT,TOP_TEXT);
  220.     outtextxy(maxX/2,10,msg);
  221.     getch();
  222. }
  223.  
  224. /*****************************************************************************/
  225. /*      Various support functions for sort routines                          */
  226. int maxkey(L, low, high)
  227. int L[], low, high;
  228. {
  229. int     m,j;
  230.  
  231.     m = low;
  232.     for (j=low+1;j<=high;j++) {
  233.         if (L[m] < L[j])
  234.             m = j;
  235.     }
  236.     return m;
  237.     
  238. }
  239.  
  240. void swap(L, x, y)
  241. int L[], x, y;
  242. {
  243. int     t;
  244.  
  245.     t = L[x];
  246.     L[x] = L[y];
  247.     L[y] = t;
  248.     update_graph(L,x);
  249.     update_graph(L,y);
  250.     
  251. }
  252.     
  253. /*****************************************************************************/
  254. /*      Perform a bubble sort on the list                                    */
  255. void bubble_sort(L, n)
  256. int L[], n;
  257. {
  258. int     i,j;
  259.  
  260.     for (i=0;i<n;i++)
  261.         for (j=i+1;j<n;j++)
  262.             if (L[i] > L[j])
  263.                 swap(L,i,j);
  264.                 
  265. }
  266.  
  267. /*****************************************************************************/
  268. /*      Perform an insertion sort on the list                                */
  269. void insertion_sort(L, n)
  270. int L[], n;
  271. {
  272. int     i,j,found,t;
  273.  
  274.     for(i=1;i<n;i++) {
  275.         if (L[i] < L[i-1]) {
  276.             j = i;
  277.             t = L[i];
  278.             do {
  279.                 j = j - 1;
  280.                 L[j+1] = L[j];
  281.                 update_graph(L,j+1);
  282.                 if (j==0)
  283.                     found = 1;
  284.                 else
  285.                     found = (L[j-1] <= t);
  286.             } while (!found);
  287.             L[j] = t;
  288.             update_graph(L,j);
  289.         }
  290.     }
  291.                     
  292. }
  293.  
  294. /*****************************************************************************/
  295. /*      Perform a selection sort on the list                                 */
  296. void selection_sort(L, n)
  297. int L[], n;
  298. {
  299. int     i,m;
  300.  
  301.     for(i=n-1;i>=1;i--) {
  302.         m = maxkey(L,0,i);
  303.         swap(L,m,i);
  304.     }
  305. }
  306.  
  307. /*****************************************************************************/
  308. /*      Perform a quick sort on the list                                     */
  309. void quick_sort(points, num)
  310. int points[], num;
  311. {
  312.         q_sort(points,0,num-1);
  313. }
  314.  
  315. void q_sort(v, left, right)
  316. int v[], left, right;
  317. {
  318. int     i,last;
  319.  
  320.     if (left >= right)
  321.         return;
  322.         
  323.     swap(v,left,right);
  324.     last = left;
  325.     for (i=left+1;i<=right;i++)
  326.         if (v[i] < v[left])
  327.             swap(v,++last,i);
  328.     swap(v,left,last);
  329.     q_sort(v,left,last-1);
  330.     q_sort(v,last+1,right);
  331.     
  332. }
  333.  
  334.